// 中心扩展法思路：1. 回文一定是对称的
// （1）每次选择一个中心，进行中心向两边扩展比较左右字符串是否相等
// （2）中心点的选择有两种
var longestPalindrome = function (s) {
  if (!s || s.length < 2) return s;
  let start = 0,
    end = 0;
  let n = s.length;
  // 中心扩展法
  let centerExpand = (left, right) => {
    while (left >= 0 && right < n && s[left] == s[right]) {
      left--;
      right++;
    }
    return right - left + 1;
  };

  for (let i = 0; i < n; i++) {
    let len1 = centerExpand(i, i);
    let len2 = centerExpand(i, i + 1);
    // 两种组合取最大回文串的长度
    let len = Math.max(len1, len2);
    if (len > end - start) {
      // 更新最大回文字符串的首尾字符索引
      start = i - ((len - 1) >> 1);
      end = i + (len >> 1);
    }

    return s.subString(start, end + 1);
  }
};

// 动态规划
// 确定 dp[i][j] 是否是回文串，只需要知道 dp[i + 1][j - 1] 是回文串并且 s[i] == s[j]
// 但是长度为 0 或 1 的回文串需要特殊处理，因此 j - i < 2
// dp[i] 需要事先知道 dp[i + 1]，所以从大到小开始遍历
// dp[j] 相反

var longestPalindrome = function (s) {
  let ans = "";
  let n = s.length;
  let dp = Array.from(new Array(n), () => new Array(n).fill(0));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]);
      if (dp[i][j] && j - i + 1 > ans.length) {
        ans = s.substring(i, j + 1);
      }
    }
  }
  return ans;
};
